1. Field of the Invention
The present invention generally relates to genetic algorithms and, more particularly, to methods and systems that utilize the concept of dominance to affect the manner in which genetic algorithms achieve a desired solution set.
2. Description of the Related Art
Computer programming searching techniques referred to as genetic algorithms are based on the concept that evolutionary principles may be applied to solve complex problems involving multiple parameters. Each parameter may be modeled as a gene having different possible gene values (or “traits”), and each individual combination of genes (hereinafter an “individual”) may be considered a candidate solution. The idea is that the population of individuals may evolve over generations, using operators inspired by natural genetic variation and natural selection, for example, based on fitness.
Typically, an initial population of individuals is defined. The fitness of the population's individuals is then evaluated based on some type of fitness evaluation function. A selection process based on this fitness evaluation is typically used to select a limited number of individuals used to produce new individuals using the standard genetic algorithm operations of crossover and mutation. These steps may be repeated to produce and evaluate future generations a set number of times or until an acceptable solution is achieved (e.g., as determined by a pre-defined threshold fitness level).
The types of evaluation functions used to determine fitness may vary widely with different applications and either lower or higher results may correspond to fitter individuals, depending on the problem being solved. For example, if the problem is to minimize material expenditures (e.g., in IC layout) or time (e.g., route scheduling), individuals with lower corresponding evaluation scores may be considered more fit. On the other hand, if the problem is to maximize a value (e.g., a score in a game or a production yield), individuals with higher corresponding evaluation scores may be considered more fit.
In either case, for some applications, it may be more desirable to reach an acceptable solution quickly rather than find an ideal solution. For example, in a computer-based gaming environment where a user is matched against a computer, the computer may be required to select an acceptable solution set for a next move in the game quickly (in “real time”). For other applications, however, time constraints may be relaxed and it may be more desirable to select an ideal solution. For example, in applications used to provide districting options for governmental entities (e.g., school or voting districts), it may be more important to achieve an optimal result even if it takes days or weeks.
Accordingly, there is a need for methods and systems that allow genetic algorithms to be optimized, for example, to improve system performance (e.g., in an effort to find an acceptable solution quickly) or to increase search space (e.g., to find an optimal solution).